package com.huhu.sort;

public class InsertSort {
    /**
     * 正常的插入排序
     * @param arr
     * @param n
     */
    public static void insertsort(int arr[],int n){
        for(int i=1;i<n;i++){
            for(int j=i;j>0;j--){
                if(arr[j]>arr[j-1]){
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
                else{
                    return;
                }
            }

        }
    }

    /**
     * 插入排序的优化
     * @param arr
     * @param r
     */
    public static void insertSort(int arr[],int r){
        int i,j,tmp;
        for (i = 1; i < r; i++) {
            tmp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = tmp;
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {5,6,5,4,3};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");

        insertsort(a,a.length);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");
    }
}
